秋招C++八股

vector和list是C++中的两种不同的容器类型，用于存储和操作元素的集合。它们有以下区别和应用：

内存结构：

Vector: Vector使用连续的内存空间存储元素，类似于数组。它可以高效地进行随机存取，时间复杂度为O(1)。插入和删除操作会导致内存块的拷贝，时间复杂度为O(n)。

List: List使用双向链表来存储元素，内存空间不连续。它的随机存取效率较低，需要遍历链表，时间复杂度为O(n)。但是插入和删除操作非常高效。 容量动态增长：

Vector: Vector具有动态增长的能力，当元素数量超过当前容量时，会自动重新分配更大的内存空间，并进行内存拷贝。程序员不需要手动处理容量问题。

List: List没有容量的限制，可以根据需要动态增长。

迭代器的有效性：

Vector: 在对Vector进行插入和删除操作后，迭代器可能会失效，需要重新定位。 List: 在对List进行插入和删除操作后，迭代器仍然有效。

查找两者的倒数第二个元素：

1

int mySize = vec.size();vec.at(mySize -2);

2

list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过 你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：

C++的vector底层通常使用动态分配的数组来实现，即连续的线性空间。下面分别介绍vector的底层实现、扩容机制和insert方法的几种情况：

底层实现：

vector内部维护一个指针，指向连续的内存空间，用于存储元素。 初始时，vector会分配一块固定大小的内存空间，可以容纳一定数量的元素。

当需要存储更多的元素时，vector会根据扩容机制重新分配更大的内存空间，并将原有元素移动到新的空间中。

扩容机制：

vector的扩容是自动进行的，它会在需要添加元素时判断当前空间是否足够。 当空间不足以容纳新元素时，vector会进行扩容操作。

扩容通常会分配一块更大的内存空间（例如原空间的两倍大小），将原有元素移动到新空间中，然后释放原空间。 扩容可能涉及到数据的复制或移动，因此会有一定的性能开销。

insert方法的几种情况：

vector的insert方法用于在指定位置插入元素，它有多个重载形式，可以根据需要插入单个元素、一定数量的元素或者另一个容器中的元素。

如果插入位置是末尾（end）之前的位置，且当前空间足够容纳新元素，那么插入操作会在指定位置直接插入元素，不会触发扩容，时间复杂度为O(1)。

如果插入位置是末尾（end）之前的位置，但当前空间不足，需要进行扩容操作，那么插入操作会在指定位置插入元素，并触发扩容。扩容操作的时间复杂度为O(n)，其中n为需要插入的元素数量。

如果插入位置是末尾（end）位置，无论当前空间是否足够，插入操作都会在末尾添加元素，不会触发扩容，时间复杂度为O(1)。

如果插入位置是其他位置（非末尾），无论当前空间是否足够，插入操作都需要将插入位置后的元素逐个向后移动，然后在指定位置插入元素，时间复杂度为O(n)，其中n为元素的数量。

向量容器vector的成员函数pop_back()可以删除最后一个元素。pop_back()会将最后一个元素从向量中移除，并且会调整向量的大小，使其减少一个元素。

函数erase()可以删除由一个iterator指向的元素，也可以删除一个指定范围的元素。erase()的用法有多种形式，可以传入一个迭代器指向要删除的元素，或者传入两个迭代器指定要删除的范围。

通用算法remove()并不能直接删除vector容器中的元素。remove()算法是用来移除容器中满足特定条件的元素，并将剩余的元素前移，返回一个指向新的逻辑末尾的迭代器。但是remove()并不会改变容器的大小，它只是移动元素并返回新的逻辑末尾位置，需要结合erase()函数来实际删除元素并改变容器大小。

pop_back()、erase()等成员函数会改变容器的大小，而remove()算法不会直接改变容器的大小，需要结合erase()函数才能删除元素并改变容器的大小。

1

vector的size()函数返回已使用的空间大小，capacity()函数返回总空间大小，而capacity() - size()表示剩余可用空间大小。

2

当size()和capacity()相等时，表示vector的空间已被用完，如果再添加新元素，则会引发vector空间的动态增长。

3

使用reserve(n)可以预先分配一块较大的指定大小的内存空间，这样在指定大小的内存空间未被使用完之前，不会引发重新分配内存空间，从而提高效率。只有当n大于capacity()时，调用reserve(n)才会改变vector的容量。

4

resize()函数只改变元素的数目，不改变vector的容量。

5

不同编译器下，vector的扩容大小可能有所不同，如在VS中为1.5倍，在GCC中为2倍。这是空间和时间的权衡，增加空间分配可以降低平摊时间复杂度，但也会浪费空间。

6

使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配 的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)

采用成倍方式扩容可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此推荐使用成倍的方式进行扩容。

使用 reserve() 函数预先分配容量为 10，然后依次向 vector 中插入 20 个元素。